package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-08 19:18
 * @description: Functions of this class is
 * 官方题解：
 * class Solution {
 * public int numSquares(int n) {
 * int[] f = new int[n + 1];
 * for (int i = 1; i <= n; i++) {
 * int minn = Integer.MAX_VALUE;
 * for (int j = 1; j * j <= i; j++) {
 * minn = Math.min(minn, f[i - j * j]);
 * }
 * f[i] = minn + 1;
 * }
 * return f[n];
 * }
 * }
 **/
public class 动态规划完全平方数 {
    //动态规划解题
    public static void main(String args[]) {
        System.out.println(numSquares(13));
    }

    public static int numSquares(int n) {
        if (n < 4) {
            return n;
        }
        int ans[] = new int[n + 1];
        ans[0] = 0;
        ans[1] = 1;
        ans[2] = 2;
        ans[3] = 3;
        for (int i = 4; i <= n; i++) {
            int minn = Integer.MAX_VALUE;
            for (int j = 1; j * j <= i; j++) {
                minn = Math.min(ans[i - (j * j)], minn);
            }
            ans[i] = minn + 1;
        }
        return ans[n];
    }
}